/**
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 */
class Solution {

    public static void main(String[] args) {
        ListNode listNodeA1 = new ListNode(1);
        ListNode listNodeA2 = new ListNode(3);
        ListNode listNodeA3 = new ListNode(5);
        ListNode listNodeB1 = new ListNode(1);
        ListNode listNodeB2 = new ListNode(3);
        ListNode listNodeB3 = new ListNode(4);
        ListNode listNodeC1 = new ListNode(2);
        ListNode listNodeC2 = new ListNode(6);
        listNodeA1.next = listNodeA2;
        listNodeA2.next = listNodeA3;
        listNodeB1.next = listNodeB2;
        listNodeB2.next = listNodeB3;
        listNodeC1.next = listNodeC2;
        ListNode[] nodes = new ListNode[]{listNodeA1, listNodeB1, listNodeC1};
        ListNode listNode = mergeKLists3(nodes);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * 时间复杂度是队列总长度*队列数，k是队列数，n是队列长度，O(kn×k)。
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        // 找到最小的节点，最小节点的下一个进入递归
        ListNode listNode = null;
        int k = -1;
        // 以下代码用于优化仅剩余一个队列的情况
        /*int x = -1;
        for (int i = 0; i < lists.length; i++) {
            if (null != lists[i]) {
                if (x == -1) {
                    x = i;
                } else {
                    x = -1;
                    break;
                }
            }
        }
        if (x != -1) {
            listNode = lists[x];
        }*/
        for (int i = 0; i < lists.length; i++) {
            if (null != lists[i]) {
                if (null == listNode) {
                    listNode = lists[i];
                    k = i;
                }
                if (lists[i].val < listNode.val) {
                    listNode = lists[i];
                    k = i;
                }
            }
        }
        if (k > -1) {
            lists[k] = lists[k].next;
            listNode.next = mergeKLists(lists);
        }
        return listNode;
    }

    /**
     * 顺序合并，有点蠢，感觉比直接合并比较次数要多，但是好像和直接合并的复杂度差不多
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists2(ListNode[] lists) {
        ListNode listNode = null;
        if (lists.length == 1) return lists[0];
        for (int i = 0; i < lists.length; i++) {
            listNode = mergeTwoLists(listNode, lists[i]);
        }
        return listNode;
    }


    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }

    /**
     * 分治法，每次都处理一半，降低的复杂度 （因为可以以logk减少比较次数）O(kn×logk)。
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists3(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }


    public static ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        if (left > right) return null;
        int mid = (left + right) / 2;
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

}